{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum XOR for Each Query"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: getMaximumXor"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #每个查询的最大异或值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个 <strong>有序</strong> 数组 <code>nums</code> ，它由 <code>n</code> 个非负整数组成，同时给你一个整数 <code>maximumBit</code> 。你需要执行以下查询 <code>n</code> 次：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li>找到一个非负整数 <code>k < 2<sup>maximumBit</sup></code> ，使得 <code>nums[0] XOR nums[1] XOR ... XOR nums[nums.length-1] XOR k</code> 的结果 <strong>最大化</strong> 。<code>k</code> 是第 <code>i</code> 个查询的答案。</li>\n",
    "\t<li>从当前数组 <code>nums</code> 删除 <strong>最后</strong> 一个元素。</li>\n",
    "</ol>\n",
    "\n",
    "<p>请你返回一个数组 <code>answer</code> ，其中<em> </em><code>answer[i]</code>是第 <code>i</code> 个查询的结果。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [0,1,1,3], maximumBit = 2\n",
    "<b>输出：</b>[0,3,2,3]\n",
    "<b>解释：</b>查询的答案如下：\n",
    "第一个查询：nums = [0,1,1,3]，k = 0，因为 0 XOR 1 XOR 1 XOR 3 XOR 0 = 3 。\n",
    "第二个查询：nums = [0,1,1]，k = 3，因为 0 XOR 1 XOR 1 XOR 3 = 3 。\n",
    "第三个查询：nums = [0,1]，k = 2，因为 0 XOR 1 XOR 2 = 3 。\n",
    "第四个查询：nums = [0]，k = 3，因为 0 XOR 3 = 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [2,3,4,7], maximumBit = 3\n",
    "<b>输出：</b>[5,2,6,5]\n",
    "<b>解释：</b>查询的答案如下：\n",
    "第一个查询：nums = [2,3,4,7]，k = 5，因为 2 XOR 3 XOR 4 XOR 7 XOR 5 = 7。\n",
    "第二个查询：nums = [2,3,4]，k = 2，因为 2 XOR 3 XOR 4 XOR 2 = 7 。\n",
    "第三个查询：nums = [2,3]，k = 6，因为 2 XOR 3 XOR 6 = 7 。\n",
    "第四个查询：nums = [2]，k = 5，因为 2 XOR 5 = 7 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [0,1,2,2,5,7], maximumBit = 3\n",
    "<b>输出：</b>[4,3,6,4,6,7]\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>nums.length == n</code></li>\n",
    "\t<li><code>1 <= n <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 <= maximumBit <= 20</code></li>\n",
    "\t<li><code>0 <= nums[i] < 2<sup>maximumBit</sup></code></li>\n",
    "\t<li><code>nums</code>​​​ 中的数字已经按 <strong>升序</strong> 排好序。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-xor-for-each-query](https://leetcode.cn/problems/maximum-xor-for-each-query/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-xor-for-each-query](https://leetcode.cn/problems/maximum-xor-for-each-query/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[0,1,1,3]\\n2', '[2,3,4,7]\\n3', '[0,1,2,2,5,7]\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:\n",
    "        a=0\n",
    "        for i in nums:\n",
    "            a^=i\n",
    "        res=[]\n",
    "        for _ in range(len(nums)):\n",
    "            k=0\n",
    "            for i in range(maximumBit-1,-1,-1):\n",
    "                if a&(1<<i)==0:\n",
    "                    k|=1<<i\n",
    "            res.append(k)\n",
    "            a^=nums.pop()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:\n",
    "        now = 0\n",
    "        n = len(nums)\n",
    "        k = (1 << maximumBit) - 1\n",
    "        ret = [0] * n\n",
    "        for i in range(n):\n",
    "            now ^= nums[i]\n",
    "            ret[i] = k ^ now\n",
    "        return ret[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:\n",
    "        ans = []\n",
    "        check = 2 ** maximumBit - 1\n",
    "        for i in range(len(nums)):\n",
    "            if i == 0:\n",
    "                xor = nums[0]\n",
    "            else:\n",
    "                xor ^=nums[i]\n",
    "            ans.insert(0, ~(xor & check) & check)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:\n",
    "        ans = []\n",
    "        check = 2 ** maximumBit - 1\n",
    "        for i in range(len(nums)):\n",
    "            if i == 0:\n",
    "                xor = nums[0]\n",
    "            else:\n",
    "                xor ^=nums[i]\n",
    "            ans.insert(0, ~ xor & check)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:\n",
    "        mask = (1 << maximumBit) - 1\n",
    "        cur = 0\n",
    "        for x in nums:\n",
    "            cur ^= x\n",
    "        \n",
    "        res = []\n",
    "        for i in range(len(nums) - 1, -1, -1):\n",
    "            res.append(~(cur & mask) & mask)\n",
    "            cur ^= nums[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:\n",
    "        tmp, target = 0, 2 ** maximumBit -1\n",
    "        for n in nums:\n",
    "            tmp ^= n\n",
    "        res = []\n",
    "        for i in range(len(nums) - 1, -1, -1):\n",
    "            res.append(target ^ tmp)\n",
    "            tmp ^= nums[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:\n",
    "        mask = (1 << maximumBit) - 1\n",
    "        cur = 0\n",
    "        for x in nums:\n",
    "            cur ^= x\n",
    "        \n",
    "        res = []\n",
    "        for i in range(len(nums) - 1, -1, -1):\n",
    "            res.append(~(cur & mask) & mask)\n",
    "            cur ^= nums[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:\n",
    "        mask = (1 << maximumBit) - 1\n",
    "        cur = 0\n",
    "        for x in nums:\n",
    "            cur ^= x\n",
    "        \n",
    "        res = []\n",
    "        for i in range(len(nums) - 1, -1, -1):\n",
    "            res.append(~(cur & mask) & mask)\n",
    "            cur ^= nums[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        mask = (1 << maximumBit) - 1\n",
    "        for i in range(1, n):\n",
    "            nums[i] ^= nums[i - 1]\n",
    "        res = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            res.append(nums[i] ^ mask)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:\n",
    "        t = 2**maximumBit - 1\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        res = [0] * n\n",
    "        for i in nums:\n",
    "            ans = ans^i\n",
    "        ans = ans ^ t\n",
    "        res[0] = ans\n",
    "        for i in range(n-1,0,-1):\n",
    "            res[n-i] = ans^nums[i]\n",
    "            ans = ans ^ nums[i]\n",
    "        return res\n",
    "\n",
    "        print(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:\n",
    "        target = (1 << maximumBit) - 1\n",
    "        ans = [*accumulate(nums, xor, initial=target)]\n",
    "        return ans[:0:-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:\n",
    "        ans = []\n",
    "        n = len(nums)\n",
    "        t = 0\n",
    "        for i in range(n):\n",
    "            t ^= nums[i]\n",
    "        for i in range(n-1, -1, -1):\n",
    "            ans.append((1<<maximumBit)-1-(t&((1<<maximumBit)-1)))\n",
    "            t ^= nums[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:\n",
    "        # 没看明白\n",
    "        res = []\n",
    "        m = 2**maximumBit-1\n",
    "        tm = 0\n",
    "        for i in range(len(nums)):\n",
    "            tm ^= nums[i]\n",
    "            res.append(tm^m)\n",
    "        return res[::-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:\n",
    "        target = (1 << maximumBit) - 1\n",
    "        ans = [*accumulate(nums, xor, initial=target)]\n",
    "        return ans[:0:-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:\n",
    "        tot = reduce(xor, nums)\n",
    "        ans = [0] * len(nums)\n",
    "        ma = (1 << maximumBit) - 1\n",
    "        for i in range(len(nums)):\n",
    "            ans[i] = xor(tot, ma)\n",
    "            tot = xor(tot, nums[len(nums) - 1 - i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:\n",
    "        target = (1 << maximumBit) - 1\n",
    "        ans = [*accumulate(nums, xor, initial=target)]\n",
    "        ans.reverse()\n",
    "        ans.pop()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:\n",
    "        result, mask = [nums[0]] * (n := len(nums)), (1 << maximumBit) - 1\n",
    "        for i in range(1, n):\n",
    "            result[i], result[i - 1] = result[i - 1] ^ nums[i], result[i - 1] ^ mask\n",
    "        result[-1] ^= mask\n",
    "        return result[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:\n",
    "        target = (1 << maximumBit) - 1\n",
    "        return [*accumulate(nums, xor, initial=target)][:0:-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:\n",
    "        target = (1 << maximumBit) - 1\n",
    "        return [*accumulate(nums, xor, initial=target)][:0:-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:\n",
    "        target = (1 << maximumBit) - 1\n",
    "        return [*accumulate(nums, xor, initial=target)][:0:-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        xor_ = reduce(xor, nums)\n",
    "        k = (1 << maximumBit) - 1\n",
    "        ans = [xor_ ^ k] * n\n",
    "        for i in range(1, n):\n",
    "            xor_ ^= nums[n - i]\n",
    "            ans[i] = xor_ ^ k\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:\n",
    "        arr, result = [nums[0]] * (n := len(nums)), (1 << maximumBit) - 1\n",
    "        for i in range(1, n):\n",
    "            arr[i], arr[i - 1] = arr[i - 1] ^ nums[i], arr[i - 1] ^ result\n",
    "        arr[-1] ^= result\n",
    "        return arr[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:\n",
    "        res, max_num, total = [], pow(2, maximumBit), 0\n",
    "        for i in range(len(nums)):\n",
    "            total ^= nums[i]\n",
    "            res.append(total^(max_num-1))\n",
    "        return res[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:\n",
    "        #考虑异或前缀和即可,没必要真的模拟删除\n",
    "        ans=[]\n",
    "        x_or,max_num=0,2**maximumBit-1\n",
    "        for num in nums:\n",
    "            x_or^=num\n",
    "            ans.append(x_or^max_num)\n",
    "        return ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:\n",
    "        target = (1 << maximumBit) - 1\n",
    "        ans = [*accumulate(nums, xor, initial=target)][::-1]\n",
    "        return ans[:-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:\n",
    "\n",
    "        xor = 0\n",
    "        ans = []\n",
    "        for i in range(len(nums)):\n",
    "            xor ^= nums[i]\n",
    "            ans.append(((1 << maximumBit) - 1) ^ xor)\n",
    "        \n",
    "        return ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:\n",
    "        #考虑异或前缀和即可,没必要真的模拟删除\n",
    "        ans=[]\n",
    "        x_or,max_num=0,2**maximumBit-1\n",
    "        for num in nums:\n",
    "            x_or^=num\n",
    "            ans.append(x_or^max_num)\n",
    "        return ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:\n",
    "        res, x = [], 0\n",
    "        for i in nums:\n",
    "            x ^= i\n",
    "            res.append('')\n",
    "            for i, j in zip(bin(x)[2:].zfill(20)[::-1], range(maximumBit)):\n",
    "                res[-1] += '0' if i=='1' else '1'\n",
    "            res[-1] = int(res[-1][::-1], 2)\n",
    "        return res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:\n",
    "        ans = []\n",
    "        n = len(nums)\n",
    "        t = 0\n",
    "        for i in range(n):\n",
    "            t ^= nums[i]\n",
    "            ans.append((1<<maximumBit)-1-(t&((1<<maximumBit)-1)))\n",
    "        return list(reversed(ans))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:\n",
    "        k = (1 << maximumBit) - 1\n",
    "        y = 0\n",
    "        ans = []\n",
    "        for x in nums:\n",
    "            y ^= x\n",
    "            ans.append(y ^ k)\n",
    "        return list(reversed(ans))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:\n",
    "        nl = len(nums)\n",
    "        for i in range(1, nl):\n",
    "            nums[i] = nums[i-1] ^ nums[i]\n",
    "        res = []\n",
    "        res.append(nums[-1] ^ (2**maximumBit - 1))\n",
    "        for i in range(nl-2, -1, -1):\n",
    "            res.append(nums[i] ^ (2**maximumBit - 1))\n",
    "        return res\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        mask = (1 << maximumBit) - 1\n",
    "        xorsum = reduce(xor, nums)\n",
    "        \n",
    "        ans = list()\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            ans.append(xorsum ^ mask)\n",
    "            xorsum ^= nums[i]\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        mask = (1 << maximumBit) - 1\n",
    "        xorsum = reduce(xor, nums)\n",
    "        \n",
    "        ans = list()\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            ans.append(xorsum ^ mask)\n",
    "            xorsum ^= nums[i]\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        mask = (1 << maximumBit) - 1\n",
    "        xorsum = reduce(xor, nums)\n",
    "        ans = list()\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            ans.append(xorsum ^ mask)\n",
    "            xorsum ^= nums[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:\n",
    "        ans = []\n",
    "        n = len(nums)\n",
    "        a = 1<<maximumBit\n",
    "        t = 0\n",
    "        for i in range(n):\n",
    "            t ^= nums[i]\n",
    "        for i in range(n-1, -1, -1):\n",
    "            ans.append(a-1-(t&(a-1)))\n",
    "            t ^= nums[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:\n",
    "        ans = []\n",
    "        check = 2 ** maximumBit - 1\n",
    "        for i in range(len(nums)):\n",
    "            if i == 0:\n",
    "                xor = nums[0]\n",
    "            else:\n",
    "                xor ^=nums[i]\n",
    "            ans.append(~ xor & check)\n",
    "            \n",
    "        return list(ans[::-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        for i in range(1, n):\n",
    "            nums[i] ^= nums[i - 1]\n",
    "        res = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            ans = 0\n",
    "            for j in range(maximumBit):\n",
    "                if (nums[i] >> j) & 1 == 0:\n",
    "                    ans += 1 << j \n",
    "            res.append(ans)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:\n",
    "        check = 2 ** maximumBit - 1\n",
    "        ans = [~nums[0] & check]\n",
    "        for i in range(1, len(nums)):\n",
    "            ans.insert(0, ans[0]^nums[i] & check)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:\n",
    "        k = nums[0]\n",
    "        for i in range(1,len(nums)):\n",
    "            k ^= nums[i]\n",
    "        res = [0] * len(nums)\n",
    "        for i in range(len(nums)-1,-1,-1):\n",
    "            x = k % (2 ** maximumBit)\n",
    "            print(x)\n",
    "            res[len(nums)-i-1] = 2 ** maximumBit - 1 -x\n",
    "            k ^= nums[i] \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        mask = (1 << maximumBit) - 1\n",
    "        xorsum = reduce(xor, nums)\n",
    "        \n",
    "        ans = list()\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            ans.append(xorsum ^ mask)\n",
    "            xorsum ^= nums[i]\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        for i in range(1, n):\n",
    "            nums[i] ^= nums[i-1]\n",
    "        res = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            temp = 0\n",
    "            for j in range(maximumBit):\n",
    "                if nums[i]>>j & 1 == 0:\n",
    "                    temp += (2 ** j)\n",
    "            res.append(temp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:\n",
    "        def check(num, n):\n",
    "            res = 0\n",
    "            for i in range(n):\n",
    "                if (num >> i) & 1 == 0:\n",
    "                    res += 1 << i \n",
    "            return res\n",
    "        n = len(nums)\n",
    "        for i in range(1, n):\n",
    "            nums[i] ^= nums[i - 1]\n",
    "        res = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            res.append(check(nums[i], maximumBit))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:\n",
    "        def check(num, n):\n",
    "            res = 0\n",
    "            for i in range(n):\n",
    "                if (num >> i) & 1 == 0:\n",
    "                    res += 1 << i \n",
    "            return res\n",
    "        n = len(nums)\n",
    "        for i in range(1, n):\n",
    "            nums[i] ^= nums[i - 1]\n",
    "        res = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            res.append(check(nums[i], maximumBit))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:\n",
    "        def check(num, n):\n",
    "            res = 0\n",
    "            for i in range(n):\n",
    "                if (num >> i) & 1 == 0:\n",
    "                    res += 1 << i \n",
    "            return res\n",
    "        n = len(nums)\n",
    "        for i in range(1, n):\n",
    "            nums[i] ^= nums[i - 1]\n",
    "        res = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            res.append(check(nums[i], maximumBit))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:\n",
    "        ans = []\n",
    "        tgt = 0\n",
    "        for i in range(maximumBit):\n",
    "            tgt = (tgt << 1) | 1\n",
    "        for i in nums:\n",
    "            tgt = tgt ^ i\n",
    "            ans.append(tgt)\n",
    "        ans.reverse()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:\n",
    "        def check(num, n):\n",
    "            res = 0\n",
    "            for i in range(n):\n",
    "                if (num >> i) & 1 == 0:\n",
    "                    res += 1 << i \n",
    "            return res\n",
    "        n = len(nums)\n",
    "        for i in range(1, n):\n",
    "            nums[i] ^= nums[i - 1]\n",
    "        res = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            res.append(check(nums[i], maximumBit))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:\n",
    "        pp=[nums[0]]\n",
    "        for i in range(1,len(nums)):\n",
    "            pp.append(pp[-1]^nums[i])\n",
    "        pp[::]=pp[::-1]\n",
    "        res=[]\n",
    "        for i in pp:\n",
    "            res.append(2**maximumBit-1-i)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:\n",
    "        n = len(nums)\n",
    "        pre = [nums[0]]\n",
    "        for x in nums[1:]:\n",
    "            pre.append(pre[-1] ^ x)\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            x = pre[n - 1 - i]\n",
    "            mx = 2 ** maximumBit - 1\n",
    "            res.append(x ^ mx)           \n",
    "        return res      "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
